package com.acwing.partition12;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2022/1/19 16:49
 */
public class AC1148秘密的牛奶运输 {

    private static final int N = 510, M = 10010;
    private static Edge[] edges = new Edge[M];
    private static int[] parent = new int[N];

    private static int[] head = new int[N], element = new int[2 * N], next = new int[2 * N], weight = new int[2 * N];
    //分别记录从u到v经过的最大边权和次大边权
    private static int[][] dist1 = new int[N][N], dist2 = new int[N][N];
    private static int n = 0, m = 0, index = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        init();
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split("\\s+");
            int u = Integer.parseInt(s[0]), v = Integer.parseInt(s[1]), w = Integer.parseInt(s[2]);
            edges[i] = new Edge(u, v, w, false);
        }
        writer.write(kruskal() + "\n");
        writer.flush();
    }

    private static void init() {
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            head[i] = -1;
        }
    }

    private static long kruskal() {
        long answer = (long) 1e18, sum = 0;
        //kruskal求最小生成树，在计算的过程中把图建立出来
        Arrays.sort(edges, 0, m, (o1, o2) -> Integer.compare(o1.w, o2.w));
        for (int i = 0; i < m; i++) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            int a = find(u), b = find(v);
            if (a != b) {
                //将该边加入到MST，并标记这个边是MST的边
                parent[a] = b;
                createEdge(u, v, w);
                createEdge(v, u, w);
                edges[i].flag = true;
                sum += w;
            }
        }
        //预处理出来任意两点之间的最大边和次大边
        for (int i = 1; i <= n; i++) dfs(i, -1, 0, 0, dist1[i], dist2[i]);
        //枚举所有非MST的边，将这个边加入到MST中，并从MST中删除一条边
        for (int i = 0; i < m; i++) {
            if (!edges[i].flag) {
                int u = edges[i].u, v = edges[i].v, w = edges[i].w;
                int t = 0;
                if (w > dist1[u][v]) t = dist1[u][v];
                else if (w > dist2[u][v]) t = dist2[u][v];
                //尽量减去u->v上较大的边，这样使得剩下的和最小，更容易构成次小生成树
                answer = Math.min(answer, sum - t + w);
            }
        }
        return answer;
    }

    private static void dfs(int u, int last, int max1, int max2, int[] dist1, int[] dist2) {
        dist1[u] = max1;
        dist2[u] = max2;
        for (int i = head[u]; i != -1; i = next[i]) {
            int v = element[i];
            if (v != last) {
                int a = max1, b = max2;
                if (weight[i] > a) {
                    b = a;
                    a = weight[i];
                } else if (weight[i] < a && weight[i] > b) {
                    b = weight[i];
                }
                dfs(v, u, a, b, dist1, dist2);
            }
        }
    }

    private static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }

    private static void createEdge(int u, int v, int w) {
        element[index] = v;
        next[index] = head[u];
        head[u] = index;
        weight[index++] = w;
    }

    private static class Edge {
        private int u, v, w;
        private boolean flag;

        public Edge(int u, int v, int w, boolean flag) {
            this.u = u;
            this.v = v;
            this.w = w;
            this.flag = flag;
        }
    }
}
